package com;

import java.util.AbstractMap;
import java.util.Set;

public class RedBlackTreeMap<Key extends Comparable<Key>, Val> extends AbstractMap<Key, Val> {

    public Node<Key, Val> root;

    public static final boolean RED = true;

    public static final boolean BLACK = false;

    public static class Node<Key, Val> {

        Key key;

        Val val;

        boolean color;

        Node<Key, Val> left;

        Node<Key, Val> right;

        Node<Key, Val> parent;

        public boolean isRED() {
            return this.color == RED;
        }

    }

    @Override
    public Set<Entry<Key, Val>> entrySet() {
        return null;
    }

    /**
     * 左旋
     *
     * @param x
     */
    private void leftRotate(Node<Key, Val> x) {

        Node<Key, Val> y = x.right;

        /**
         * 把 y 的 左节点移动到 x 的右节点上
         */
        x.right = y.left;

        if (y.left != null) {
            /*
             * 如果y有左子节点，那么就把 y 的左子节点的父节点指向 x
             * 因为经过上一行移动 y 的左子节点之后，y的左子节点已经属于 x 了
             * */
            y.left.parent = x;
        }

        // 把 y 的父节点指向 x 的父节点
        y.parent = x.parent;

        if (x.parent == null) {
            // x 没有 父节点的话，那么x就是根节点
            // 左旋之后 y 会上升，所以根节点就变成了 y
            root = y;

        } else

            // x 不是root节点，那么就把x的父节点的左、右子节点指向 y
            if (x == x.parent.left) {
                x.parent.left = y;
            } else {
                x.parent.right = y;
            }
        /**
         * 完成左旋的最后两个步骤
         *
         */
        y.left = x;
        x.parent = y;
    }

    /**
     * 右旋
     *
     * @param y
     */
    private void rightRotate(Node<Key, Val> y) {

        Node<Key, Val> x = y.left;

        y.left = x.right;

        if (x.right != null) {
            x.right.parent = y;
        }

        if (y.parent == null) {
            root = x;
        }

        x.parent = y.parent;

        if (y == y.parent.left) {
            y.parent.left = x;
        } else {
            y.parent.right = x;
        }

        x.right = y;
        y.parent = x;
    }

    /**
     * 将z插入到树的空叶子节点
     *
     * @param z
     */
    private void insert(Node<Key, Val> z) {
        // 要插入这个节点的目标位置
        Node<Key, Val> location = this.root;
        // 目标位置的父节点
        Node<Key, Val> targetParent = null;

        int compareResult = 0;

        while (location != null) {
            /**
             * 更新目标节点的父节点
             * 循环，直到找到一个空的叶子节点，能把新节点放入这个位置
             */
            targetParent = location;
            compareResult = location.key.compareTo(z.key);
            if (compareResult > 0) {
                location = location.left;
            } else {
                location = location.right;
            }
        }
        z.parent = targetParent;
        if (targetParent == null) {
            this.root = z;
        } else if (compareResult > 0) {
            targetParent.left = z;
        } else {
            targetParent.right = z;
        }

        z.left = null;
        z.right = null;
        z.color = RED;
    }


    private void insertFixup(Node<Key, Val> z) {
        if (z.parent == null || z.parent.parent == null) {
            return;
        }

        while (z.parent.color = RED) {
            Node<Key, Val> uncle = null;
            if (z.parent == z.parent.parent.left) {
                // 父节点在祖父节点的左边
                // 获得叔节点（叔节点在父节点的右边）
                uncle = z.parent.parent.right;

            } else {


                // 父节点在祖父节点的右边
                // 获得叔节点（叔节点在父节点的左边）
                uncle = z.parent.parent.left;

            }

            z = getKeyValNode(z, uncle);

        }
    }

    private Node<Key, Val> getKeyValNode(Node<Key, Val> z, Node<Key, Val> uncle) {
        if (uncle != null && uncle.color == RED) {
            /**
             * 情况一：父节点和叔节点都是红色的，并且z节点也是红色的
             * 出现了连续的红色节点（本节点和父节点连续为红色），
             * 而且不能简单的将本节点和父节点进行左旋、右旋，因为左右旋之后，本节点和父节点互换位置，还是有连续的红节点
             * 也不能将父节点和祖父节点左旋、右旋，因为这么做了之后，
             * 原来的祖父节点变成了红色，虽然本节点和父节点不是连续的红色（父节点旋转后变成了黑色），
             * 但是祖父节点和叔节点成为了连续的红色，破坏了红黑树的性质。
             * <p>
             * 正确的做法：将父节点和叔节点的颜色（红色）同时网上移动，祖父节点变成红色，
             * 然后祖父节点原来的黑色往下移动，使得父节点和叔节点变为黑色，此时就不存在连续的红色节点了
             * 且保持了任意叶子节点的黑高都一致
             */

            z.parent.color = BLACK;
            uncle.color = BLACK;
            z.parent.parent.color = RED;
            z = z.parent.parent;
        } else if (z == z.parent.right) {
            // 情况二：当前节点是父节点的右节点
            // 左旋之后使其和情况三相同

            // 将z往上移动一层
            z = z.parent;
            // 左旋之后，z的位置下来了
            leftRotate(z);
        }

        /**
         * 因为情况二、情况三的叔节点是黑色的，这就意味着
         * 只要父节点为黑色、祖父节点为红色，那么就不会有连续的红节点
         * 因为叔节点是黑色。
         * 步骤：将父节点的颜色（红色）上移，父节点和祖父节点交换颜色
         */
        z.parent.color = BLACK;
        z.parent.parent.color = RED;
        /**
         * 此时祖父节点为红色，可以针对祖父节点执行一个右旋
         * 此时祖父节点变成父节点的右节点，
         * 没有连续的红节点，左旋之后也能保证各叶子节点的黑高相同
         */
        rightRotate(z.parent.parent);
        return z;
    }

    @Override
    public Val put(Key key, Val value) {

        Node<Key, Val> z = new Node<>();
        z.key = key;
        z.val = value;
        insert(z);
        // 插入之后 z 为红色节点，可能会违反红黑树的性质，所需需要修复红黑树
        insertFixup(z);

        return value;
    }


}
